1. Field of the Invention
The present invention relates to logical circuit design, and in particular the invention is directed to an asynchronous pulse logic circuit.
2. Background Art
VLSI (Very Large Scale Integration) system design is the process of implementing and realizing a system specification, the architecture, as an electronic circuit. We shall assume that the architecture is given to us and that the fabrication is not our concern. Longtime tradition divides the design process into two stages beyond computer architecture: implementation of the architecture by a micro-architecture and realization of the micro-architecture by a physical circuit design. The border is an artificial demarcation drawn for political purposes. The VLSI border traditionally serves to separate high-level logical reasoning from electronic-circuit design, tasks usually performed by different people, or at least by different software systems.
From Physics to Computer Science
It has slowly been realized that, as Carver Mead suggested, VLSI system design contains aspects of both software design and electrical engineering. In VLSI, the imagination of the mathematician and enthusiasm of the programmer finally meet with the pragmaticism of the engineer. c, we are told, is the speed limit; λ is the accuracy that we can build things with. But most of us would rather ignore the problems of others. So when we imagine and program a VLSI system, we do not allow c and λ to constrain our imagination or to damp our enthusiasm. We design our systems as if c and λ did not exist, and then we tell the engineer, “Implement this.” When the wafers return, we say that the poor performance is not our fault: we cannot be blamed for any failure to deal with c and λ since we left this task to our friend, the engineer.
Asynchronous Digital Design
Poor performance is usually unacceptable for a VLSI system. Optimists have long studied asynchronous design techniques, hoping that they have found at least a partial solution to the design problem. While it is true that proponents of asynchronous design like claiming that asynchronous circuits offer speed and power advantages, the main advantage of asynchronous design is more subtle than these: it is the designer's ability of easily composing circuits that operate at different points in the design space (characterized by speed, power, and design effort) without destroying the beneficial properties of any of the circuits.
A system is asynchronous if, in short, it does not use a clock for sequencing its actions. What unites all methods of asynchronous circuit design is that they all strive for making the speed of computing dependent on the operations that are being carried out. A slow operation is allowed to take longer than a fast one; the system continues to the next operation only once the previous one is completed. It is as if we could assemble a troika consisting of an Arabian, a Shetland pony, and a draught horse, without losing the useful qualities of the individual horses. If we should try this with real horses, the harness would act much as the clock does in a synchronous system and render the exercise pointless. But the asynchronous troika may be able to pull its load better than even a well-matched synchronous team, because the horses are not harnessed together by the clock—the draught horse does not have to keep up with the Arabian, and we do not have to feed the big horses if we only have need for the pony. By allowing us to divide up a system into smaller, more independent pieces, the asynchronous design technique simplifies the large-system design problem.
Asynchronous Design-styles
In a synchronous system, it is easy to know when a computation is done. When the clock edge arrives, we read out the results of the computation. If it is not finished by then, we say that the system is wrong and throw it on the trash heap. (Or—less violently—adjust the clock speed.) The computation must necessarily be done by the time the clock edge arrives, or else the synchronous model would not make sense.
In contrast, the chief difficulty in asynchronous design is knowing when a specific computation is done. If we encode data in the same way as in a synchronous system, e.g., using two's—complement numbers, and start an operation, and the number “5” should appear on the result bus of our asynchronous system, how are we to know that it signifies the result of the present computation, and not of the previous? Worse, might it not be the bitwise combination of the results of the previous and current computations?
Bundled-data Design
The early asynchronous computers were designed in what we shall call the bundled-data style. Designing in this style, the designer assumes that he can build a delay that matches whatever the delay is of the computation that he is really interested in. This matched delay is used as an “alarm clock” that is started when ƒ(x) is started and that rings when we can be sure that ƒ(x) has been completely computed. The design style is called bundled data because the data travels in a “bundle” whose timing is governed by the control signal that we called the “alarm clock.” As one might guess, arranging for the matched delay is the Achilles' heel of the bundled-data style. If the delay is too short, the system will not work; if too long, then it will work slowly. Especially if computation times are data-dependent, the matched delay can easily become a designer's nightmare. The matched delay mechanism's working rests on a form of a priori knowledge of relative timing; we shall call making use of such knowledge a timing assumption.
Delay-insensitive Design-styles
Originally conceived of at about the same time as the bundled-data design-style, delay-insensitive logic design attempts using the data bits themselves for sequencing. By making every input transition (change in logic level) cause, either in itself or within a cohort of input transitions, an output transition or a detectable pattern of output transitions, we can at least make interfaces between processes delay-insensitive.
Systems built using the delay-insensitive philosophy range from the speed-independent investigated by D. E. Muller in the 1950's, which work under the assumption that all wire delays are negligible compared with the operator delays (which may be of any length), to the truly delay-insensitive, in which both operator delays and wire delays may be arbitrary. Martin has shown that, using a reasonable operator model, truly delay-insensitive systems are of little use; the work in our research group has mainly been within the quasi delay-insensitive (QDI) model, which is essentially Muller's speed-independent model with information added for distinguishing between wires whose delays must be short compared with the operator delays and wires whose delays may be arbitrarily long.
Assembling a working system out of QDI parts is almost frighteningly easy: start from a correct sequential program, decompose it into communicating processes, compile these processes into circuits, put the pieces together, and everything works. The chief advantage of this design method is that once we have decomposed, the design style is completely modular: there is no implicit use of global information (i.e., no clock), and the different parts can be designed independently.
There is one difficulty with QDI design: the requirement that the circuits work properly even if all operator delays were to vary unboundedly is a difficult one to satisfy; our satisfying it involves inserting much circuitry whose only purpose is checking for the occurrences of transitions that we may know would in any case take place. We should say that QDI systems must still be designed “within reason”: it is possible to make things not work by designing them very poorly; likewise, it still takes considerable work and skill to achieve good performance.